/********************************
* 2、编写一个算法，对顺序入栈的序列
*（入栈序列a,b,c,…，）进行判断，
* 检查出不可能的出栈顺序。
********************************/

#include<stdio.h>
#include<malloc.h>
#include<string.h>

int print = 1;

typedef struct {int* data;int capacity,top; } stack;

stack* stack_new(int capacity){
    stack* s = malloc(sizeof(stack));
    s->capacity = capacity;
    s->top = 0;
    s->data = malloc(sizeof(int)*capacity);
    return s;
}

void stack_del(stack* s){free(s->data);free(s);}

int stack_pop(stack* s){
    if(s->top==0){perror("Empty stack");return 0;}
    return s->data[--s->top];
}

void stack_push(stack* s,int data){if(s->top < s->capacity)s->data[s->top++] = data;}



// given a sequence of 1-n, check whether it is legal
int check(int* seq,int n){
    int cur,i,a,b; cur = i = a = b = 0;
    stack* s = stack_new(n);
    while(cur < n){
        a = seq[cur++];
        if(s->top!=0 && a == s->data[s->top-1] ){ stack_pop(s); continue; }
        if(i==n || a<=i){free(s);return 0;}
        while( a > ++i )stack_push(s,i);
    }
    free(s);return 1;
}

int main(int argc,char** argv){
    if(argc==2 && strcmp(argv[1],"--no-print")==0)print=0;
    int i,n;
    int A[1024];
    if(print)printf("n=");
    while(scanf("%d",&n)==1){
        if(print)printf("Enter n integers: ");
        for(i=0;i<n;i++)scanf("%d",A+i);
        printf("%d\n",check(A,n));
        if(print)printf("n=");
    }
    return 0;
}